package leetcode2;

public class Day1 {
    //10.正则表达式匹配
    public boolean isMatch(String ss, String pp) {
        int m=ss.length(),n=pp.length();
        ss = "_"+ss;
        pp = "_"+pp;
        boolean[][] dp = new boolean[m+1][n+1];
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //1.初始化
        dp[0][0]=true;
        for(int j=2;j<=n;j+=2) {
            if(p[j] == '*') dp[0][j]=true;
            else break;
        }
        //2.从上往下，从左往右填表
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                if(p[j]=='*') {
                    dp[i][j]= dp[i][j-2] || (p[j-1]=='.' || p[j-1]==s[i]) && dp[i-1][j];
                }else {
                    dp[i][j]= (p[j]==s[i] || p[j]=='.') && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
